/*
*
* A星算法类
* */

class AStar {
    constructor(gridData) {
        this.gridData = gridData;
        this.path = [];  //当前算法算出的最短路径
        this.openList = []; //已经估价过的节点列表
        this.closeList = []; // 作为代价最小节点评估过周围八个顶点
        this.straightCost = 1; //直线代价值
        this.diagCost = Math.sqrt(2); //斜线的代价值

        this.heuristic = this.manhattan; //设置当前算法使用到的计算当前节点到终点的估价函数
    }

    //传入gridData，获取当前路径
    findPath() {
        //重置化一些配置
        this.openList = []; //已经估价过的节点列表
        this.closeList = []; // 作为代价最小节点评估过周围八个顶点
        this.startNode = this.gridData.startNode;
        this.endNode = this.gridData.endNode;
    }

    //
    search() {
        //首先设置初始节点的代价
        this.startNode.g = 0;
        this.startNode.h = this.heuristic(this.startNode);
        this.startNode.f = this.startNode.g + this.startNode.h;

        //从起点开始遍历，获取到最短路径
        let node = this.startNode;
        while (node !== this.endNode) {
            const startX = Math.max(0, node.x - 1);
            const startY = Math.max(0, node.y - 1);
            const endX = Math.min(this.gridData.cols - 1, node.x + 1);
            const endY = Math.min(this.gridData.rows - 1, node.y + 1);

            for (let i = startX; i <= endX; i++) {
                for (let j = startY; j <= endY; j++) {
                    const searchNode = this.gridData.getNode(i, j);
                    if (searchNode === node || !searchNode.walkable || /*this.isOpen(searchNode) ||*/ this.isClose(searchNode)) continue;
                    //计算当前节点的代价
                    let cost = this.straightCost;
                    if (searchNode.x !== node.x && searchNode.y !== node.y) {
                        cost = this.diagCost;
                    }

                    const g = node.g + cost;
                    const h = this.heuristic(searchNode);
                    const f = g + h;

                    //有些算法是需要额外判断open列表，来查看是否需要更新
                    if (this.isOpen(searchNode)) {
                        //如果此节点处于open列表中，则对当前值和原有值进行判断，是否需要更新
                        if (searchNode.g > g) {
                        //if (searchNode.f > f) {
                            searchNode.g = g;
                            searchNode.h = h;
                            searchNode.f = f;
                            searchNode.parent = node;
                        }
                    }
                    else {
                        searchNode.g = g;
                        searchNode.h = h;
                        searchNode.f = f;
                        searchNode.parent = node;
                        this.openList.push(searchNode);
                    }
                }
            }

            this.closeList.push(node);

            //如果openList内的列表已经为空，则直接退出
            if (this.openList.length === 0) {
                console.warn('无法找到路径！！！');
                return false;
            }

            //以代价从小到大进行排序
            this.openList.sort(function (a, b) {
                return a.f - b.f;
            });

            //修改node为代价最小的节点
            node = this.openList.shift();
        }

        //构建路径
        this.buildPath();

        return true;
    }

    //构建路径
    buildPath() {
        //从终点向它的父元素去寻找最短路径
        const path = [];
        let node = this.endNode;
        path.push(node);
        while (node !== this.startNode) {
            node = node.parent;
            path.unshift(node);
        }

        this.path = path;
    }

    //获取到当前生成的路径
    getPath() {
        return this.path;
    }

    //获取到此次寻路被访问的节点
    getVisited() {
        return this.openList.concat(this.closeList);
    }

    //判断是否是已经估价过的节点
    isOpen(node) {
        return this.openList.indexOf(node) > -1;
    }

    //判断是否已经作为小代价评估过周围八个顶点
    isClose(node) {
        return this.closeList.indexOf(node) > -1;
    }

    //勾股定理 获取当前节点到结束位置的距离
    gouGu(node) {
        const dx = node.x - this.endNode.x;
        const dy = node.y - this.endNode.y;

        return Math.sqrt(dx * dx + dy * dy);
    }

    //曼哈顿估价当前点到终点
    manhattan(node) {
        const dx = node.x - this.endNode.x;
        const dy = node.y - this.endNode.y;
        return Math.abs(dx) * this.straightCost + Math.abs(dy) * this.straightCost;
    }

    //对角线估价函数
    diagonal(node) {
        const dx = Math.abs(node.x - this.endNode.x);
        const dy = Math.abs(node.y - this.endNode.y);
        const diag = Math.min(dx, dy);
        return diag * this.diagCost + this.straightCost * Math.abs(dx - dy); //本人的写法
        //return diag*this.diagCost + this.straightCost * (dx+dy - 2*diag);  //教程的写法
    }
}

module.exports = AStar;